Teoria degli ordini

La teoria degli ordini è un ramo della matematica, e in particolare dell'algebra, che studia le relazioni d'ordine tra elementi di un insieme. Un ordine è una relazione binaria che mette in relazione coppie di elementi secondo criteri di confronto, come "minore o uguale" nei numeri o "essere contenuto in" tra insiemi. Quando tale relazione è riflessiva, antisimmetrica e transitiva, si parla di ordine parziale; se invece ogni coppia di elementi è confrontabile, si ha un ordine totale. La teoria degli ordini fornisce strumenti per analizzare strutture come insiemi ordinati, reticoli e gerarchie, ed è fondamentale in ambiti che vanno dalla logica matematica all'informatica teorica.

In particolare, è il fondamento della semantica denotazionale dei linguaggi di programmazione: come vedremo, le definizioni ricorsive (di funzioni, di tipi di dato, di insiemi definiti per induzione) trovano il loro significato come punti fissi di opportune funzioni su domini ordinati. Tutto il percorso che segue, dai poset alle CPO, fino al Teorema di Kleene, serve esattamente a dare un senso preciso e calcolabile all'idea di "soluzione di un'equazione ricorsiva".

Poset

Un poset (dall'inglese partially ordered set, "insieme parzialmente ordinato") è una coppia $(P, ⊑)$ formata da un insieme $P$ e da una relazione di ordine parziale $⊑ \subseteq P \times P$ definita su di esso.

La relazione $⊑$ deve essere:

- riflessiva, per ogni $x \in P$ , $x ⊑ x$ ;

- antisimmetrica, se $x ⊑ y$ e $y ⊑ x$ , allora $x = y$ ;

- transitiva, se $x ⊑ y$ e $y ⊑ z$ , allora $x ⊑ z$ .

Scriviamo $x ⊑ y$ per dire che $x$ e $y$ sono confrontabili e che $x$ è minore o uguale a $y$ . Con $x ⊏ y$ intendiamo invece la parte stretta della relazione, ovvero $x ⊑ y \land x \neq y$ .

A differenza degli insiemi totalmente ordinati, in un poset non tutte le coppie di elementi devono essere confrontabili: può accadere che esistano elementi $a$ e $b$ per cui né $a ⊑ b$ né $b ⊑ a$ sono veri. In tal caso si dice che $a$ e $b$ sono inconfrontabili.

I poset possono essere rappresentati graficamente tramite diagrammi di Hasse, che omettono gli archi resi impliciti dalla riflessività (i cappi su ogni nodo) e dalla transitività (gli archi "scorciatoia"), mostrando solo le relazioni di copertura immediate. Per convenzione, se $x ⊑ y$ allora $x$ è disegnato più in basso di $y$ .

Ordini totali, discreti e piatti

Alcune famiglie particolari di poset meritano un nome proprio.

Gli ordini totali sono poset in cui ogni elemento è confrontabile con qualsiasi altro elemento dell'insieme:

$\forall p, q \in P . p ⊑ q \lor q ⊑ p$

Il loro diagramma di Hasse è una semplice catena verticale.

Gli ordini discreti sono poset in cui ogni elemento è confrontabile esclusivamente con sé stesso:

$\forall p, q \in P . p ⊑ q \Leftrightarrow p = q$

Il diagramma di Hasse è una "polvere" di punti isolati, senza alcun arco.

I flat order (ordini "piatti") sono poset in cui ciascun elemento è confrontabile con sé stesso e con un singolo elemento, minore di tutti gli altri, detto bottom e indicato col simbolo $⊥$ :

$\forall p, q \in P . p ⊑ q \Leftrightarrow p = q \lor p = ⊥$

Il diagramma di Hasse è un "ventaglio" di punti tutti collegati direttamente a un unico elemento inferiore $⊥$ . Gli ordini piatti sono il modo standard per trasformare un insieme "non ordinato" $A$ in un dominio: si aggiunge un elemento $⊥$ che rappresenta il valore indefinito (il calcolo che non termina), ottenendo $A_{⊥} = A \cup {⊥}$ .

Domanda per il lettore. $(ℕ, \leq)$ è un poset? È totale, discreto, piatto? E $(ℕ, <)$ ? E ancora $(ℕ, =)$ e $(ℕ, \neq)$ ? Indizio: provate a rappresentare ciascuna relazione con il suo diagramma di Hasse, e ricordate che l'ordine deve essere riflessivo.

Un altro esempio fondamentale è l'insieme delle parti $(℘ (S), \subseteq)$ di un insieme $S$ : è un poset (l'inclusione è riflessiva, antisimmetrica e transitiva), ma non è totale appena $| S | \geq 2$ , perché ad esempio ${a}$ e ${b}$ sono inconfrontabili.

Sottoinsiemi e ordine inverso

Gli ordini si comportano bene rispetto alle due operazioni più naturali: restringere l'insieme e invertire la relazione.

Teorema (sottoinsieme di un poset). Sia $(P, ⊑_{P})$ un poset e $Q \subseteq P$ . Posto $⊑_{Q} ≜ ⊑_{P} \cap (Q \times Q)$ , la coppia $(Q, ⊑_{Q})$ è ancora un poset. Inoltre, se $(P, ⊑_{P})$ è totale, allora anche $(Q, ⊑_{Q})$ lo è.

In altre parole: qualsiasi sottoinsieme di un ordine totale è un ordine totale. La dimostrazione è immediata, dato che riflessività, antisimmetria, transitività e totalità sono proprietà universali, e quindi "ereditate" da ogni sottoinsieme.

Teorema (ordine inverso). Se $(P, ⊑)$ è un poset, allora lo è anche $(P, ⊒)$ , dove $⊒ = ⊑^{- 1}$ è la relazione inversa. La verifica è immediata: riflessività, antisimmetria e transitività sono simmetriche rispetto all'inversione. Questo principio di dualità è prezioso: ogni nozione che introdurremo "verso il basso" (elemento minimo, bottom, minorante) ha una nozione duale "verso l'alto" (elemento massimo, top, maggiorante) che si ottiene gratuitamente leggendo le definizioni nell'ordine inverso.

Poset e relazioni ben fondate

È istruttivo confrontare gli ordini parziali $(⊑)$ con le relazioni ben fondate $(≺)$ , quelle su cui si fonda il principio di induzione ben fondata. Sono oggetti per molti versi opposti.

Un poset $⊑$ è:

- riflessivo;

- antisimmetrico;

- transitivo;

- può ammettere catene discendenti infinite (si pensi a $(ℤ, \leq)$ , dove $\dots ⊏ - 2 ⊏ - 1 ⊏ 0$ ).

Una relazione ben fondata $≺$ è invece:

- non riflessiva, teorema importantissimo: se lo fosse, $x ≺ x$ darebbe immediatamente un ciclo, e quindi una catena discendente infinita, contraddicendo la ben fondatezza;

- antisimmetrica, ma in modo vacuo: $x ≺ y \land y ≺ x$ è sempre falso (origina un ciclo);

- per essa esiste la chiusura transitiva $≺^{+}$ , anch'essa ben fondata;

- non ammette alcuna catena discendente infinita, è esattamente questa la proprietà che la definisce.

Il legame tra i due mondi è il seguente: la chiusura riflessiva e transitiva $≺^{*}$ di una relazione ben fondata è sempre un poset, e viceversa la parte stretta $⊏$ di un poset può, in casi favorevoli (ad esempio i poset in cui non esistono catene discendenti infinite), essere ben fondata.

Elementi notevoli

Fissato un poset $(P, ⊑)$ e un sottoinsieme $Q \subseteq P$ , possiamo individuare alcuni elementi che giocano un ruolo speciale. Le definizioni vanno lette con cura, perché differenze apparentemente minime (minimo vs minimale) hanno conseguenze importanti.

Elemento minimo e bottom

Un elemento $ℓ \in Q$ è il minimo (least element) di $Q$ se è minore o uguale di ogni elemento di $Q$ :

$\forall q \in Q . ℓ ⊑ q$

Si noti la richiesta forte: $ℓ$ deve essere confrontabile con tutti gli elementi di $Q$ , e stare sotto a ciascuno.

Teorema (unicità del minimo). Se $ℓ_{1}$ e $ℓ_{2}$ sono entrambi minimi di $Q$ , allora $ℓ_{1} = ℓ_{2}$ .

Dimostrazione. Poiché $ℓ_{1}$ è minimo, $ℓ_{1} ⊑ ℓ_{2}$ . Poiché $ℓ_{2}$ è minimo, $ℓ_{2} ⊑ ℓ_{1}$ . Per antisimmetria, $ℓ_{1} = ℓ_{2}$ . $■$

Quando esiste, il minimo dell'intero insieme $P$ prende il nome di bottom e si indica con $⊥$ (talvolta $⊥_{P}$ per disambiguare). Per esempio, in $(℘ (S), \subseteq)$ il bottom è $\emptyset$ ; in $(ℕ \cup {\infty}, \leq)$ il bottom è $0$ .

Elemento minimale

Un elemento $m \in Q$ è minimale se nessun elemento di $Q$ sta strettamente sotto di esso:

$\forall q \in Q . q ⊑ m \Rightarrow q = m$

Intuitivamente, sotto a $m$ non si trova nulla di confrontabile, ma potrebbero esistere elementi inconfrontabili con $m$ .

Nel poset $(℘ ({a, b, c}) ∖ {\emptyset}, \subseteq)$ , ad esempio, i singoletti ${a}, {b}, {c}$ sono tutti minimali, ma nessuno è il minimo (sono inconfrontabili tra loro). Se invece aggiungiamo $\emptyset$ , allora $\emptyset$ diventa l'unico minimale e contemporaneamente il minimo.

Massimo, top e massimali (per dualità)

Tutte le nozioni precedenti hanno un duale, ottenuto leggendole nell'ordine inverso $⊒$ :

- l'elemento massimo (greatest element) di $Q$ è il minimo di $Q$ rispetto a $⊒$ , cioè un elemento maggiore o uguale di tutti gli altri;

- il top $⊤$ è il massimo dell'intero $P$ (se esiste);

- un elemento massimale è un minimale rispetto a $⊒$ , cioè un elemento sopra al quale non c'è nulla di strettamente più grande e confrontabile.

In $(℘ (S), \subseteq)$ il top è $S$ stesso; in $(ℕ \cup {\infty}, \leq)$ il top è $\infty$ .

Maggioranti e minimo dei maggioranti (lub)

Le nozioni di minimo/massimo richiedono che l'elemento speciale appartenga a $Q$ . Spesso però vogliamo "rappresentare $Q$ dall'alto" con un elemento che può stare anche fuori da $Q$ : nasce così la nozione di maggiorante.

Un elemento $u \in P$ è un maggiorante (upper bound) di $Q$ se tutti gli elementi di $Q$ gli stanno sotto:

$\forall q \in Q . q ⊑ u$

Si noti che $u$ non deve necessariamente appartenere a $Q$ , e che $Q$ può avere molti maggioranti (o anche nessuno).

Tra tutti i maggioranti, quello più informativo è il più piccolo. Un elemento $p \in P$ è il minimo dei maggioranti o estremo superiore (least upper bound, lub) di $Q$ se:

1. è un maggiorante di $Q$ : $\forall q \in Q . q ⊑ p$ ;

2. è minore o uguale di ogni altro maggiorante: $\forall u \in P . (\forall q \in Q . q ⊑ u) \Rightarrow p ⊑ u$ .

Scriviamo $p = ⨆ Q$ . Intuitivamente, il lub è il più piccolo elemento che "rappresenta tutto $Q$ dall'alto". Come per il minimo, quando esiste il lub è unico (stessa dimostrazione per antisimmetria). Attenzione: il lub, se esiste, non appartiene necessariamente a $Q$ .

Esempi.

- In $(ℕ, \leq)$ , un sottoinsieme $Q$ finito ha lub $\max Q$ ; un sottoinsieme infinito non ha lub (l'insieme dei maggioranti è vuoto).

- In $(℘ (S), \subseteq)$ , ogni famiglia $Q \subseteq ℘ (S)$ ha lub, ed è l'unione: $⨆ Q = ⋃_{T \in Q} T$ . Per esempio $⨆ {{a}, {b}} = {a, b}$ .

- Esistono poset in cui un insieme ha maggioranti ma nessun lub, perché tra i maggioranti non ce n'è uno minimo (due maggioranti inconfrontabili e "minimali" tra i maggioranti).

Per dualità si definisce il massimo dei minoranti o estremo inferiore (greatest lower bound, glb o meet), indicato con $bigsqcap Q$ . Un poset in cui ogni sottoinsieme ammette sia lub sia glb è un reticolo completo.

Catene e limiti

Per la semantica dei linguaggi non ci interessa tanto il lub di un insieme arbitrario, quanto il lub di una particolare famiglia ordinata: la catena. L'idea guida è quella di approssimazione.

> L'idea di completezza. Pensiamo a $P$ come a un dominio di significati e leggiamo $x ⊑ y$ come " $x$ è un'approssimazione (meno precisa) di $y$ ": $x$ e $y$ sono consistenti, ma $y$ è più accurato. Una computazione produce allora una successione crescente di approssimazioni

> $x_{0} ⊑ x_{1} ⊑ x_{2} ⊑ \dots ⊑ x_{n} ⊑ \dots$

> e la domanda naturale è: questa successione di approssimazioni tende a un limite? La completezza è esattamente la garanzia che la risposta sia sempre sì.

Una catena in un poset $(P, ⊑)$ è una successione ${d_{i}}_{i \in ℕ}$ tale che

$d_{0} ⊑ d_{1} ⊑ d_{2} ⊑ \dots ⊑ d_{n} ⊑ \dots ovvero \forall i \in ℕ . d_{i} ⊑ d_{i + 1}$

Per convenzione una catena è sempre una lista infinita di elementi (non necessariamente distinti). Una catena si dice finita se contiene solo un numero finito di elementi distinti, cioè se da un certo punto in poi diventa costante:

$\exists k \in ℕ . \forall i \geq k . d_{i} = d_{k}$

Il limite di una catena ${d_{i}}_{i \in ℕ}$ è il suo estremo superiore, quando esiste, e lo indichiamo con

$⨆_{i \in ℕ} d_{i}$

Esempio. In $(ℕ, \leq)$ la catena $0 \leq 2 \leq 4 \leq \dots \leq 2 n \leq \dots$ non ha limite (nessun maggiorante), mentre $0 \leq 1 \leq 3 \leq 3 \leq 5 \leq \dots \leq 5 \leq \dots$ è finita e ha limite $5$ .

Due lemmi semplici ma fondamentali rendono i limiti maneggevoli.

Lemma (catene finite). In ogni poset, ogni catena finita ha limite, ed è il suo ultimo (massimo) elemento.

Dimostrazione. Se la catena è definitivamente costante a $d_{k}$ , allora $d_{k}$ è il massimo della catena (gli elementi sono totalmente ordinati tra loro), quindi ne è un maggiorante; ed è il minimo dei maggioranti, perché ogni maggiorante $u$ soddisfa $d_{k} ⊑ u$ . $■$

Lemma (indipendenza dal prefisso). Se la catena ${d_{i}}_{i \in ℕ}$ ha limite, allora per ogni $k$ anche la catena "spostata" ${d_{i + k}}_{i \in ℕ}$ ha lo stesso limite:

$⨆_{i \in ℕ} d_{i + k} = ⨆_{i \in ℕ} d_{i}$

Dimostrazione. Basta mostrare che le due catene hanno gli stessi maggioranti (e quindi lo stesso minimo dei maggioranti). Ogni maggiorante di ${d_{i}}$ è maggiorante di ${d_{i + k}}$ , perché quest'ultima è un sottoinsieme della prima. Viceversa, se $u$ è maggiorante di ${d_{i + k}}$ e $j < k$ , allora $d_{j} ⊑ d_{k} ⊑ u$ , quindi $u$ maggiora anche i primi $k$ termini. $■$

Il secondo lemma formalizza un'intuizione importante: il limite di una computazione dipende solo dal suo comportamento "a lungo termine", non da quanto fatto in un numero finito di passi iniziali.

Ordini parziali completi (CPO)

Un poset $(P, ⊑)$ è detto completo (complete partial order, CPO) se ogni catena in esso ha un limite (least upper bound).

Un semplice esempio è $(ℕ \cup {\infty}, \leq)$ , dotato di un elemento top, per l'appunto $\infty$ : l'insieme dei numeri dispari ha lub $\infty$ , l'insieme dei numeri pari ha lub $\infty$ , e ogni catena infinita ha limite $\infty$ .

Dal lemma sulle catene finite discende una serie di condizioni sufficienti molto comode:

- ogni catena finita ha limite (è il suo ultimo elemento);

- se $P$ ammette solo catene finite, allora è completo;

- ogni poset finito è completo;

- ogni ordine discreto è completo (le uniche catene sono costanti);

- ogni flat order è completo (le uniche catene sono costanti o $⊥ ⊑ a ⊑ a ⊑ \dots$ ).

Controesempio. $(ℕ, \leq)$ non è completo: la catena $0 \leq 2 \leq 4 \leq \dots$ non ha limite. Per esibire la non completezza basta sempre una singola catena senza limite. Analogamente, $(ℕ \cup {\infty_{1}, \infty_{2}}, \leq)$ con due elementi massimali inconfrontabili non è completo: una catena infinita ha come maggioranti sia $\infty_{1}$ sia $\infty_{2}$ , ma questi sono inconfrontabili, quindi non esiste il minimo dei maggioranti.

CPO con bottom (CPO $_{⊥}$ )

Una CPO con bottom, scritta CPO $_{⊥}$ , è una CPO che possiede anche l'elemento minimo $⊥$ . Il bottom rappresenta l'approssimazione "vuota", il punto di partenza di ogni computazione: l'informazione nulla, da cui ogni successione di approssimazioni prende le mosse. Come vedremo, la presenza di $⊥$ è ciò che garantisce l'esistenza dei punti fissi (Teorema di Kleene).

Esempi importanti di domini.

- Insieme delle parti. $(℘ (S), \subseteq)$ è una CPO $_{⊥}$ con bottom $\emptyset$ . Il limite di una catena di insiemi è la loro unione: $⨆_{i} S_{i} = ⋃_{i} S_{i} = {x ∣ \exists k . x \in S_{k}}$ .

- Numeri naturali estesi. $(ℕ \cup {\infty}, \leq)$ è una CPO $_{⊥}$ con bottom $0$ e top $\infty$ .

- Ordini piatti. Per ogni insieme $A$ , il dominio piatto $A_{⊥} = A \cup {⊥}$ è una CPO $_{⊥}$ . È il modo canonico di interpretare un tipo di dato "con possibilità di non terminazione".

Funzioni parziali come dominio

L'esempio cardine per la semantica è il dominio delle funzioni parziali. Scriviamo $f : A ⇀ B$ (oppure $f : A \to B \cup {⊥}$ ) per una funzione che può essere indefinita su alcuni ingressi. Vista come relazione, una funzione parziale è l'insieme delle coppie in cui è definita:

$f = {(a, f (a)) ∣ a \in A, f (a) \neq ⊥} \subseteq A \times B$

Sull'insieme $P_{f} (A, B)$ delle funzioni parziali da $A$ a $B$ definiamo l'ordine

$f ⊑ g \Leftrightarrow \forall a \in A . (f (a) ↓ \Rightarrow g (a) ↓ \land f (a) = g (a))$

dove $f (a) ↓$ significa " $f$ è definita su $a$ ". A parole: $g$ raffina $f$ , cioè $g$ è definita ovunque lo è $f$ e vi assume lo stesso valore (ma può essere definita anche dove $f$ non lo è). Vista la rappresentazione insiemistica, questo equivale semplicemente all'inclusione $f \subseteq g$ .

Si verifica facilmente che $(P_{f} (A, B), ⊑)$ è una CPO $_{⊥}$ :

- il bottom è la relazione vuota, cioè la funzione ovunque indefinita;

- è completa, perché il limite di una catena ${f_{i}}$ è $⋃_{i} f_{i}$ , che è ancora una funzione (la proprietà funzionale si conserva: se $(a, b_{1})$ e $(a, b_{2})$ stanno nell'unione, esistono indici $k, h$ in cui compaiono, e in $f_{\max {k, h}}$ , funzione, vale $b_{1} = b_{2}$ ).

Un'osservazione tanto semplice quanto profonda: il limite di una catena di funzioni parziali può essere una funzione totale. È proprio così che approssimazioni finite "convergono" a una funzione completa, per esempio, la successione

$\emptyset ⊑ {(0, 1)} ⊑ {(0, 1), (1, 1)} ⊑ {(0, 1), (1, 1), (2, 2)} ⊑ {(0, 1), (1, 1), (2, 2), (3, 6)} ⊑ \dots$

ha come limite la funzione fattoriale, totale.

Le funzioni totali $A \to B$ si ottengono come caso particolare: $P_{f} (A, B) ≅ A \to B_{⊥}$ , dove $B_{⊥}$ ha l'ordine piatto, e l'ordine punto a punto $f ⊑ g \Leftrightarrow \forall a . f (a) ⊑_{B_{⊥}} g (a)$ rende anche questo un dominio completo, con limite calcolato punto a punto.

Funzioni tra domini

Una volta stabilito cosa sono i domini, dobbiamo capire quali funzioni tra di essi "rispettano la struttura". Ne servono due livelli: la monotonia e la continuità.

Funzioni monotone

Date due CPO $(D, ⊑_{D})$ e $(E, ⊑_{E})$ , una funzione $f : D \to E$ è monotona se preserva l'ordine:

$\forall d_{1}, d_{2} \in D . d_{1} ⊑_{D} d_{2} \Rightarrow f (d_{1}) ⊑_{E} f (d_{2})$

Monotona = preserva l'ordine. L'intuizione è che più informazione in ingresso non può che dare più informazione in uscita: raffinando l'argomento, il risultato si raffina (o resta invariato). Una conseguenza immediata e indispensabile è che una funzione monotona manda catene in catene: se ${d_{i}}$ è una catena in $D$ , allora ${f (d_{i})}$ è una catena in $E$ .

Teorema (composizione). La composizione di funzioni monotone è monotona. Se $f : D \to E$ e $g : E \to F$ sono monotone, lo è anche $g \circ f : D \to F$ .

Funzioni continue

La monotonia non basta: vogliamo che la funzione "commuti con il passaggio al limite". Date due CPO $D$ ed $E$ , una funzione monotona $f : D \to E$ è continua se preserva i limiti delle catene:

$\forall {d_{i}}_{i \in ℕ} catena . f (⨆_{i \in ℕ} d_{i}) = ⨆_{i \in ℕ} f (d_{i})$

Continua = preserva i limiti. Si noti che, grazie alla monotonia, una delle due disuguaglianze è gratuita: $⨆_{i} f (d_{i}) ⊑ f (⨆_{i} d_{i})$ vale sempre. La continuità chiede in più la disuguaglianza opposta, cioè che $f$ non "salti" al limite, introducendo informazione non prevista da nessuna approssimazione finita.

Quando monotonia e continuità coincidono.

Lemma. Se $D$ è una CPO senza catene infinite (ad esempio finita, o discreta, o piatta) ed $E$ è una CPO, allora ogni funzione monotona $f : D \to E$ è automaticamente continua.

Dimostrazione. Ogni catena ${d_{i}}$ è finita, quindi definitivamente costante a $d_{k} = ⨆_{i} d_{i}$ ; per monotonia ${f (d_{i})}$ è anch'essa definitivamente costante a $f (d_{k})$ , da cui $⨆_{i} f (d_{i}) = f (d_{k}) = f (⨆_{i} d_{i})$ . $■$

La distinzione diventa quindi interessante solo in presenza di catene infinite. Su $(ℕ \cup {\infty}, \leq)$ , ad esempio, la funzione

$f (x) = {\begin{cases} 0 se x \in ℕ \\ 1 se x = \infty \end{cases}$

è monotona ma non continua: presa la catena $d_{i} = 2 \cdot i$ con limite $⨆_{i} d_{i} = \infty$ , si ha $f (⨆_{i} d_{i}) = f (\infty) = 1$ , mentre $⨆_{i} f (d_{i}) = ⨆_{i} 0 = 0 \neq 1$ . La funzione "vede" il limite $\infty$ ma nessuna delle approssimazioni finite lo annuncia.

Teorema (composizione). La composizione di funzioni continue è continua.

Punti fissi e Teorema di Kleene

Arriviamo al cuore del discorso. Una definizione ricorsiva ha la forma

$p = f (p)$

una "equazione" in cui l'oggetto cercato $p$ compare a entrambi i membri. Esempi: la definizione di una funzione che richiama sé stessa, di un processo che si riavvia, di un insieme chiuso rispetto a certe regole. Le domande sono due: esiste un tale $p$ ? Esiste il più piccolo? La teoria dei punti fissi risponde a entrambe.

Sia $f : D \to D$ una funzione su una CPO. Diciamo che:

- $p \in D$ è un punto fisso (fixpoint) di $f$ se $f (p) = p$ ;

- $p \in D$ è un pre-punto fisso (pre-fixpoint) di $f$ se $f (p) ⊑ p$ .

Ovviamente ogni punto fisso è anche un pre-punto fisso. L'idea di Kleene è di costruire il punto fisso iterando $f$ a partire dal nulla, cioè da $⊥$ . Definiamo la potenza $f^{n}$ per applicazione ripetuta:

$f^{0} (d) = d, f^{n + 1} (d) = f (f^{n} (d))$

Lemma (la catena di Kleene). Se $D$ è una CPO $_{⊥}$ e $f : D \to D$ è monotona, allora ${f^{n} (⊥)}_{n \in ℕ}$ è una catena.

Dimostrazione. Per induzione su $n$ proviamo $f^{n} (⊥) ⊑ f^{n + 1} (⊥)$ . Caso base: $f^{0} (⊥) = ⊥ ⊑ f^{1} (⊥)$ , perché $⊥$ è il minimo. Passo induttivo: se $f^{n} (⊥) ⊑ f^{n + 1} (⊥)$ , applicando $f$ (monotona) otteniamo $f^{n + 1} (⊥) ⊑ f^{n + 2} (⊥)$ . $■$

Poiché $D$ è completa, questa catena ha un limite, ed è il candidato punto fisso.

Teorema (del punto fisso di Kleene). Sia $D$ una CPO $_{⊥}$ e $f : D \to D$ una funzione continua. Posto

$fix (f) ≜ ⨆_{n \in ℕ} f^{n} (⊥)$

valgono:

1. $fix (f)$ è un punto fisso di $f$ , cioè $f (fix (f)) = fix (f)$ ;

2. $fix (f)$ è il minimo pre-punto fisso di $f$ : per ogni $d \in D$ , se $f (d) ⊑ d$ allora $fix (f) ⊑ d$ . In particolare è il minimo punto fisso.

Dimostrazione del punto 1. Sfruttando la continuità e l'indipendenza dal prefisso:

$f (fix (f)) = f (⨆_{n} f^{n} (⊥)) = ⨆_{n} f (f^{n} (⊥)) = ⨆_{n} f^{n + 1} (⊥) = ⨆_{n} f^{n} (⊥) = fix (f)$

Dimostrazione del punto 2. Sia $d$ un pre-punto fisso, $f (d) ⊑ d$ . Proviamo per induzione che $f^{n} (⊥) ⊑ d$ per ogni $n$ : il caso base è $f^{0} (⊥) = ⊥ ⊑ d$ ; il passo induttivo usa monotonia e l'ipotesi $f^{n} (⊥) ⊑ d$ per ottenere $f^{n + 1} (⊥) = f (f^{n} (⊥)) ⊑ f (d) ⊑ d$ . Dunque $d$ è un maggiorante della catena di Kleene, e poiché $fix (f)$ ne è il minimo maggiorante, $fix (f) ⊑ d$ . $■$

Il teorema è il motore della semantica denotazionale: dà esistenza, unicità del minimo e, soprattutto, un metodo costruttivo per calcolare il significato di una definizione ricorsiva, iterando $f$ a partire da $⊥$ .

Esempi di calcolo del punto fisso

Lavoriamo nelle CPO $_{⊥}$ già viste, controllando ogni volta monotonia e continuità.

- $f (n) = 2 \cdot n$ su $(ℕ \cup {\infty}, \leq)$ , con $f (\infty) = \infty$ . Si ha $f^{0} (0) = 0$ , $f^{1} (0) = 0$ : punto fisso raggiunto subito, $fix (f) = 0$ .

- $f (n) = n + 1$ su $(ℕ \cup {\infty}, \leq)$ , con $f (\infty) = \infty$ . Qui $f^{0} (0) = 0, f^{1} (0) = 1, f^{2} (0) = 2, \dots$ La catena $0 ⊑ 1 ⊑ 2 ⊑ \dots$ ha limite $fix (f) = ⨆_{n} n = \infty$ : il punto fisso si raggiunge "all'infinito".

- $f (X) = X \cup {1}$ su $(℘ (ℕ), \subseteq)$ . $f^{0} (\emptyset) = \emptyset$ , $f^{1} (\emptyset) = {1}$ , $f^{2} (\emptyset) = {1}$ : punto fisso ${1}$ .

- Attenzione alla non monotonia. $f (X) = ℕ ∖ X$ su $(℘ (ℕ), \subseteq)$ non è monotona (più grande è $X$ , più piccolo è $f (X)$ ): $f^{0} (\emptyset) = \emptyset$ , $f^{1} (\emptyset) = ℕ$ , $f^{2} (\emptyset) = \emptyset$ , … non è nemmeno una catena, e Kleene non si applica.

Un esempio celebre e meno banale è la funzione 91 di McCarthy, vista come trasformazione $M$ sul dominio $P_{f} (ℕ, ℕ)$ :

$M (f) (n) = {\begin{cases} n - 10 se n > 100 \\ f (f (n + 11)) se n \leq 100 e f (n + 11) ↓ \\ ⊥ altrimenti \end{cases}$

Iterando $M$ a partire da $⊥$ (la funzione ovunque indefinita) la catena cresce dapprima sui valori $> 100$ , poi "scende" colmando progressivamente gli ingressi minori, fino a raggiungere un punto fisso che è una funzione totale: vale $n - 10$ per $n > 100$ e costantemente $91$ per $n \leq 100$ .

Operatore delle conseguenze immediate (ICO)

Concludiamo con l'applicazione che chiude il cerchio tra teoria degli ordini, logica e induzione: i sistemi di regole di inferenza. Una definizione induttiva (l'insieme dei numeri pari, le stringhe ben parentesizzate, la relazione di transizione di un linguaggio…) è data da un insieme $R$ di regole del tipo

$\frac{x_{1} \dots x_{n}}{y}$

con $n$ premesse $x_{1}, \dots, x_{n}$ e una conclusione $y$ (gli assiomi sono le regole con $n = 0$ ). La domanda è: qual è l'insieme dei teoremi generati da $R$ ? La teoria dei punti fissi dà una risposta precisa.

Sia $F$ l'insieme di tutte le formule; allora $(℘ (F), \subseteq)$ è una CPO $_{⊥}$ . L'operatore delle conseguenze immediate (Immediate Consequences Operator, ICO) associato a $R$ è la funzione $\hat{R} : ℘ (F) \to ℘ (F)$ definita da

$\hat{R} (S) ≜ {y | \exists \frac{x_{1} \dots x_{n}}{y} \in R . {x_{1}, \dots, x_{n}} \subseteq S}$

A parole: $\hat{R} (S)$ è l'insieme di tutte le conclusioni ottenibili applicando le regole un solo passo a partire dalle ipotesi già presenti in $S$ .

L'operatore gode delle proprietà giuste:

- $\hat{R}$ è monotono. Se $S_{1} \subseteq S_{2}$ e $y \in \hat{R} (S_{1})$ , la regola che produce $y$ ha premesse in $S_{1} \subseteq S_{2}$ , quindi $y \in \hat{R} (S_{2})$ .

- $\hat{R}$ è continuo, a patto che ogni regola abbia un numero finito di premesse. Questa ipotesi di finitezza è esattamente ciò che serve: data una catena ${S_{i}}$ e una conclusione $y$ ottenibile da $⋃_{i} S_{i}$ , le sue (finite) premesse compaiono tutte già in qualche $S_{k}$ con $k = \max {k_{1}, \dots, k_{n}}$ , quindi $y \in \hat{R} (S_{k})$ .

Definiamo ora l'insieme dei teoremi "per livelli": $I_{R}^{0} = \emptyset$ e $I_{R}^{n + 1} = I_{R}^{n} \cup \hat{R} (I_{R}^{n})$ (i teoremi dimostrabili con una derivazione alta al più $n$ ). Si dimostra per induzione che $I_{R}^{n} = \hat{R^{n}} (\emptyset)$ , e quindi l'insieme di tutti i teoremi è

$I_{R} = ⋃_{n \in ℕ} I_{R}^{n} = ⋃_{n \in ℕ} \hat{R^{n}} (\emptyset)$

Teorema. Se ogni regola ha un numero finito di premesse, l'insieme dei teoremi di $R$ è il minimo punto fisso dell'operatore delle conseguenze immediate:

$fix (\hat{R}) = I_{R}$

Dimostrazione. Per il Teorema di Kleene (applicabile perché $\hat{R}$ è continuo su una CPO $_{⊥}$ ), $fix (\hat{R}) = ⨆_{n} \hat{R^{n}} (\emptyset) = ⋃_{n} \hat{R^{n}} (\emptyset) = I_{R}$ . $■$

Questo risultato è la giustificazione formale del principio di induzione sulle regole: l'insieme definito induttivamente è il più piccolo insieme chiuso rispetto alle regole, ovvero il minimo punto fisso di $\hat{R}$ .

Esempio (stringhe ben parentesizzate). Sull'alfabeto ${(,)}$ definiamo il linguaggio $L$ con le regole

$\frac{}{ε \in L} \frac{s \in L}{(s) \in L} \frac{s_{1} \in L s_{2} \in L}{s_{1} s_{2} \in L}$

Iterando l'ICO da $\emptyset$ si ottiene:

${\hat{R}}^{0} (\emptyset) = \emptyset, {\hat{R}}^{1} (\emptyset) = {ε}, {\hat{R}}^{2} (\emptyset) = {ε, ()}, {\hat{R}}^{3} (\emptyset) = {ε, (), (()), () ()}, \dots$

e il limite di questa catena è esattamente $L$ , l'insieme di tutte e sole le stringhe ben parentesizzate.

In sintesi

1. I poset danno una nozione di confronto e di approssimazione tra elementi.

2. Catene, maggioranti e lub formalizzano l'idea di limite di una successione di approssimazioni.

3. Le CPO $_{⊥}$ garantiscono che ogni catena converga e forniscono un punto di partenza $⊥$ .

4. Le funzioni monotone e continue sono quelle che rispettano questa struttura.

5. Il Teorema di Kleene assicura che ogni funzione continua su una CPO $_{⊥}$ abbia un minimo punto fisso, calcolabile iterando da $⊥$ .

6. L'ICO mostra che gli insiemi definiti induttivamente sono minimi punti fissi, unificando teoria degli ordini, logica e induzione.

Questa stessa macchina ricompare altrove: la bisimilarità tra processi, ad esempio, si definisce proprio come punto fisso (in quel caso massimo, su una CPO costruita ad hoc) di un funzionale continuo, applicando ancora una volta il Teorema di Kleene.